#include<iostream>
#include<unordered_map>
#include<vector>
#include<unordered_set>
using namespace std;

class Solution21 {
public:
    unordered_map<char, int> hasht;
    unordered_map<char, int> hashs;
    unordered_set<char> rem;
    int lent;
    bool judge(const string& t) {
        for (auto& ch : rem) {
            if (hashs[ch] < hasht[ch])
                return false;
        }
        return true;
    }

    string minWindow(string s, string t) {
        lent = t.size();
        for (auto& ch : t) {
            hasht[ch]++;
            rem.insert(ch);
        }
        int len = s.size();
        int anslen = 2000000000;
        int ans_left = 0;
        int left = 0, right = 0;
        for (right = left; right < len; right++) {
            hashs[s[right]]++;
            while (judge(t)) {
                if (right - left + 1 < anslen) {
                    anslen = right - left + 1;
                    ans_left = left;
                }
                hashs[s[left]]--;
                left++;
            }
        }
        if (anslen == 2000000000)
            anslen = 0;
        return s.substr(ans_left, anslen);
    }
};

class Solution1 {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else return mid;
        }
        return -1;
    }
};

class Solution2 {
public:
    int mySqrt(int x) {
        long long left = 0, right = x;
        long long mid = (left + right) / 2;
        long long ans = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            if (mid * mid > x) {
                right = mid - 1;
            }
            else if (mid * mid <= x) {
                ans = mid;
                left = mid + 1;
            }
        }
        return ans;
    }
};


class Solution3 {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        std::ios_base::sync_with_stdio(false);

        int left = 0;
        int right = arr.size() - 1;
        while (left < right) {
            auto mid = left + ((right - left) >> 1);
            if (arr[mid + 1] > arr[mid]) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return left;
    }
};

class Solution11 {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        int mid = (left + right) / 2;
        while (left < right) {
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            }
            else if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            }
        }
        return mid;
    }
};

int main()
{
    vector<int> vt = { 1,2,3,1 };
    int ans = Solution11().findPeakElement(vt);

    return 0;
}

class Solution {
public:
    int findMin(vector<int>& nums) {
        if (nums[nums.size() - 1] > nums[0]) {
            return nums[0];
        }
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return nums[left];
    }
};

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int i;
        for (i = 0; i < records.size(); i++) {
            if (i != records[i]) {
                return i;
            }
        }
        return i;
    }
};

class Solution {
public:
    int takeAttendance(vector<int>& records) {
        int left = 0, right = records.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (mid == records[mid]) {
                left = mid + 1;
            }
            else {
                right = mid;
            }
        }
        return left;
    }
};